

<p><span style="font-size: small;">Exercice 1 : &Eacute;crire une fonction "Implique(a,b)" qui vaut True si a=&gt;b, False sinon.</span></p>

{{{id=0|
def Implique(a,b): return (not a or b)
///
}}}

<p><span style="font-size: small;">Exercice 2 : On repr&eacute;sente une formule logique &agrave; deux inconnues par une fonction &agrave; deux arguments </span><span id="cell_outer_3"><span style="font-size: small;">({Vrai, Faux}&sup2; -&gt; {Vrai, Faux})</span></span><span style="font-size: small;">. &Eacute;crire une fonction qui prend</span> <span id="cell_outer_3"><span style="font-size: small;">en entr&eacute;e deux telles formules et qui teste si elles sont &eacute;quivalentes.</span></span></p>
<p><span style="font-size: small;">&nbsp;</span><span id="cell_outer_3"><span style="font-size: small;"><br /></span></span></p>

{{{id=27|
def Equiv(f,g):
    for a in [True, False]:
        for b in [True, False]:
            if f(a,b)!=g(a,b): return False
    return True
///
}}}

<p><span style="font-size: small;"><br /></span></p>

<p><span style="font-size: small;">Exercice 3  :  Construire une fonction, qui prend en entr&eacute;e une formule logique et  qui imprime sa table de  v&eacute;rit&eacute; (de taille 4). </span></p>

{{{id=31|
def TableVerite(f):
    print '  a   |    b   |   f(a,b) '
    for a in [True, False]:
        for b in [True, False]:
            print a,' | ',b,' | ',f(a,b)
            
TableVerite(Implique)
///
  a   |    b   |   f(a,b) 
True  |  True  |  True
True  |  False  |  False
False  |  True  |  True
False  |  False  |  True
}}}

<p><span style="font-size: small;">Exercice 4 (*) : M&ecirc;me question, mais l'entr&eacute;e est un entier n et une fonction &agrave; n arguments. Pour ce faire, sachez que * transforme une liste en arguments pour une fonction : par exemple, si args = [1,2,3], alors f(*args) = f(1,2,3).<br /></span></p>

{{{id=21|
def TableVeriten(n,f):
    args = [False]*n
    print args, f(*args)
    for i in range(2**n-1): 
        k=0
        while args[k]:
            args[k] = False
            k+=1
        args[k] = True
        print args, f(*args)
///
}}}

{{{id=68|
def and_imply(a,b,c): return Implique(a and b, c)
///
}}}

{{{id=66|
TableVeriten(3,and_imply)
///
[False, False, False] True
[True, False, False] True
[False, True, False] True
[True, True, False] False
[False, False, True] True
[True, False, True] True
[False, True, True] True
[True, True, True] True
}}}

<p><span style="font-size: small;">Exercice 5 (**) : On prend en entr&eacute;e une cha&icirc;ne de caract&egrave;res de la forme "(p ou q) =&gt; r", bien parenth&eacute;s&eacute;e (o&ugrave; on admet que non, ou, et, =&gt;, &lt;=&gt; sont des mots-cl&eacute;s, et les autres lettres des propositions). On veut obtenir une table de v&eacute;rit&eacute; compl&egrave;te. Bon courage !</span></p>

{{{id=70|
# Fonctions examples
def implies(a,b):
    if a==True: return bool(b)
    return True

def equiv(a,b): return a==b

def unhappy(a,b): return False

logic={'ou':'or','et':'and','modulo':'%','vrai':'True','faux':'False'} #Absolument non necessaire si l'on ne souhaite ecrire en français
functions={'<=>': equiv,'=>':implies,'=/':unhappy} #Nb, le dictionnaire contient des fonctions pas des chaines

def clever_eval(text):
    "Evalue l'expression entrée. Retourne une valeur de verité."
    status=True
    if ')' in text: # Parenthésage prime sur les fonctions !
        i=text.index(')')
        j=text[:i].rindex('(')
        return clever_eval(text[j+1:i])
    for fun  in functions:
        if fun in text:
            text=text.split(fun,1)
            return functions[fun](clever_eval(text[0]),clever_eval(text[1])) # By the almighty recursion !
    if status:
        for fun in logic:
            text=text.replace(fun,logic[fun])
        return eval(text) # Puissance de python: Faire le job pour moi

def replace(expression,valeurs):
    pass
def table_expression(expression,variables,typ=int):
    """<expression>,<variables> - Table de verité de l'expression <expression> en fonction des variables <variables>"""
    bin_max,var_max,binary=2**(len(variables)),len(variables),0
    expression=' '+expression+' '
    separator='+'+'-'*(9+len(expression)+var_max)+'+'
    print separator
    print '| Table of truth'+' '*(-7+len(expression)+var_max)+' |'
    print '|'+' '*(7+var_max)+'  %s'%expression+'|'
    print separator
    while binary<bin_max:
        i,temp_expression=0,expression
        while i<var_max:
            temp_expression=temp_expression.replace(' %s '%variables[i],' %s '%int(bin(binary+bin_max)[i+3]))
            i+=1
        try:
            print '|',bin(bin_max+binary)[3:],'|',temp_expression,'|',int(clever_eval(temp_expression)),'|'
        except:
            print "Verifiez que toutes vos variables sont declarées comme variables et séparées par des espaces"
            return False
        binary+=1
    print separator
print clever_eval.__doc__
print clever_eval(" ( 1 => 1) => False")

table_expression(" a or ( b => c )",['a','b','c'])
table_expression(" a or b => 0",['a','b'])
///
Evalue l'expression entrée. Retourne une valeur de verité.
True
Tables de verité
+------------------------------+
| Table of truth               |
|              a or ( b => c ) |
+------------------------------+
| 000 |   0 or ( 0 => 0 )  | 1 |
| 001 |   0 or ( 0 => 1 )  | 1 |
| 010 |   0 or ( 1 => 0 )  | 0 |
| 011 |   0 or ( 1 => 1 )  | 1 |
| 100 |   1 or ( 0 => 0 )  | 1 |
| 101 |   1 or ( 0 => 1 )  | 1 |
| 110 |   1 or ( 1 => 0 )  | 0 |
| 111 |   1 or ( 1 => 1 )  | 1 |
+------------------------------+
+-------------------------+
| Table of truth          |
|             a or b => 0 |
+-------------------------+
| 00 |   0 or 0 => 0  | 1 |
| 01 |   0 or 1 => 0  | 0 |
| 10 |   1 or 0 => 0  | 0 |
| 11 |   1 or 1 => 0  | 0 |
+-------------------------+
}}}

{{{id=71|
bin(2**8)[3]
///
'0'
}}}

<p><span style="font-size: medium;"><strong>Deuxi&egrave;me partie : ensembles.</strong></span></p>
<p><span style="font-size: small;">On </span><span style="font-size: small;">va essayer de mod&eacute;liser des ensembles avec des structures de donn&eacute;es qui ne sont pas forc&eacute;ment faites pour &ccedil;a, &agrave; savoir des listes (d'entiers). Dans la suite, quand on parlera d'ensemble, on voudra dire liste sans prendre en compte les r&eacute;p&eacute;titions ou l'ordre des entr&eacute;es. Dans la vraie vie, Sage utilise aussi les listes pour mod&eacute;liser des ensembles vie l'op&eacute;ration "set".</span></p>

<p><span style="font-size: small;">Exercice 5 : &Eacute;crivez une fonction qui prend en entr&eacute;e un ensemble E et un pr&eacute;dicat p (c'est-&agrave;-dire ici une fonction N -&gt; {True, False}), et qui v&eacute;rifie si on a "Pour tout x dans E, p(x)".</span> <span style="font-size: small;">Renvoyez juste True ou False.</span></p>

{{{id=51|
def PourTout(E,p):
    for x in E:
        if not p(x): return False
    return True
///
}}}

<p><span style="font-size: small;">Exercice 6 : &Eacute;crivez une fonction qui prend en entr&eacute;e deux ensembles </span><span style="font-size: small;">et qui &eacute;crit leur produit cart&eacute;sien. Un couple est bien d&eacute;fini en Python et s'&eacute;crit simplement (a,b).</span></p>

{{{id=63|
def ProduitCartesien(E,F):
    ExF=[]
    for x in E:
        for y in F:
            ExF.append((x,y))
    return ExF
///
}}}

<p><span style="font-size: small;">Exercice 7 : &Eacute;crivez une fonction qui prend en entr&eacute;e deux ensembles et qui teste s'ils sont &eacute;gaux, sans les modifier.</span></p>

{{{id=34|
def Egaux(E,F):
    for x in E:
        if not (x in F): return False
    for y in F:
        if not (y in E): return False
    return True
///
}}}

<p><span style="font-size: small;">Exercice 8 : &Eacute;crivez une fonction qui, &eacute;tant donn&eacute; en entr&eacute;e deux ensembles A et B et une fonction f, v&eacute;rifie qu'on a bien f(A) inclus dans B, et indique si f est injective, surjective ou bijective.</span></p>

{{{id=30|
def fdeAdansB(A,B,f):
    for x in A:
        if not (f(x) in B): return false
    return True
    
def InjSurjBij(A,B,f):
    Inj = True
    Surj = True
    for y in B:
        nbAntecedents = 0
        for x in A:
            if f(x) == y: 
                nbAntecedents = nbAntecedents+1
        if nbAntecedents == 0: Surj = 0
        elif nbAntecedents >1: Inj = 1
    if (not fdeAdansB(A,B,f)): print 'On a un problème de définition'
    elif Inj and Surj: print 'La fonction est surjective !'
    elif Inj: print 'La fonction est injective !'
    elif Surj: print 'La fonction est surjective !'
    else: print 'C est une fonction, c est déjà ça.'
///
}}}

<p><span style="font-size: small;">Exercice 9 : &Eacute;crivez un fonction qui "nettoie" un ensemble, c'est-&agrave;-dire qui supprime les doublons. Vous pouvez utiliser une fonction appartient(E,x,i) qui teste si l'&eacute;l&eacute;ment x fait partie des i premiers &eacute;l&eacute;ments de E. Si vous &ecirc;tes perfectionniste, il existe une fonction qui trie les listes (trouvez-la).</span></p>

{{{id=20|
def appartient(E,x,i):
        for k in range(i):
            if E[k]==x: return True
        return False
def appartient(E,x,i): return x in E[:i]
def Nettoie(E):
    resultat = []
    for i in range(len(E)):
        if (not appartient(E,E[i],i)): resultat.append(E[i])  
    return resultat
///
}}}

<p><span style="font-size: small;">On va repr&eacute;senter une relation comme une fonction qui prend en entr&eacute;e deux entiers et renvoie True ou False.</span></p>
<p><span style="font-size: small;">Exercice 10 : &Eacute;crivez une fonction qui prend en entr&eacute;e un ensemble et une relation et qui teste si elle est r&eacute;flexive, sym&eacute;trique et/ou transitive.</span></p>

{{{id=16|
def Relation(E,r):
    Refl, Sym, Trans = True, True, True
    for x in E:
        if not r(x,x): Refl = False
    for x in E:
        for y in E:
            if r(x,y) and not r(y,x): Sym = False
    for x in E:
        for y in E:
            for z in E:
                if r(x,y) and r(y,z) and not r(x,z): Trans = False
    return (Refl, Sym, Trans)
///
}}}

{{{id=64|
def r(a,b): return False
E = [1,2,3,4]
Relation(E,r)
///
(False, True, True)
}}}

<p><span style="font-size: small;">Puis, &eacute;tant donn&eacute; un ensemble et une relation d'&eacute;quivalence, passez l'ensemble au quotient.</span></p>

{{{id=24|
def Quotient(E,r):
    quotient = []
    for x in E:
        NouvelleClasse = True
        for y in quotient:
            if r(x,y[0]): 
                y.append(x)
                NouvelleClasse = False
        if NouvelleClasse: quotient.append([x])
    return quotient
///
}}}

{{{id=65|
def r(a,b): return (a-b)%2 == 0
E = [1,2,3,4]
Quotient(E,r)
///
[[1, 3], [2, 4]]
}}}

<p><span style="font-size: small;">Exercice 11 (*) : &Eacute;crivez une fonction qui, prenant en entr&eacute;e quatre ensembles A, B, A', B' et deux fonctions f : A -&gt; A' et g : B -&gt; B', renvoie la fonction produit (x,y) -&gt; (x', y'). Attention : cette fonction ne prend qu'un seul argument, et cet argument est un couple.</span></p>

{{{id=37|
def Produit(f,g):
    def h(x):
        a,b = x
        return (f(a),g(b))
    return h
///
}}}

<p><span style="font-size: small;">Exercice 12 (*) : Construire la fonction qui &agrave; un ensemble associe l'ensemble de ses parties.</span></p>

{{{id=13|
def Parties(E):
    E = Nettoie(E)
    n = len(E)
    include = [False]*n
    parties = []
    def ajoute_partie():
        p = []
        for i in range(n):
            if include[i]: p.append(E[i])
        parties.append(p)
    ajoute_partie()
    for i in range(2**n-1): 
        k=0
        while include[k]:
            include[k] = False
            k+=1
        include[k] = True
        ajoute_partie()
    return parties
///
}}}

{{{id=69|
Parties([1,2,3])
///
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
}}}

<p><span style="font-size: small;">Bonus comique pour la fin : vous vous rappelez que je vous ai expliqu&eacute; que Vrai pouvait s'&eacute;crire 1 et que Faux pouvait s'&eacute;crire 0 ?</span></p>

{{{id=45|
False == 0
///
True
}}}

{{{id=43|
True + 2
///
3
}}}

{{{id=67|

///
}}}